package com.dycong.common.dataStructuresAndAlgorithms.sort;

/**
     * A class that contains several sorting routines,
     * implemented as static methods.
     * Arrays are rearranged with smallest item first,
     * using compareTo.
     * @author Mark Allen Weiss
     */
    public final class Sort
    {
        /**
         * Simple insertion sort.
         * @param a an array of Comparable items.
         */
        public static void insertionSort( Comparable [ ] a )
        {
            int j;

/* 1*/      for( int p = 1; p < a.length; p++ )
            {
/* 2*/          Comparable tmp = a[ p ];
                /*todo 每次只按照从下标p->0(不满足条件tmp.compareTo( a[ j - 1 ] )会中断)操作，符合条件即交换，a[p]的值交换(a[ j ] = a[ j - 1 ]其实是前值赋后值,直到最后不再移动时a[ j ] = tmp将原来的a[p]赋给最后被copy到下一个的a[j])一次前进一次，*/
                /*todo 直到出现一次不满足条件(tmp.compareTo( a[ j - 1 ] )或j=0)循环就结束，不负责单词排序未涉及到的最前边，*/
                /*todo 会在刚开始时排序好前边的(从起始位置开始的排序)，之后出现小于很靠前之前的数，会连续前移的!!!*/
/* 3*/          for( j = p; j > 0 && tmp.compareTo( a[ j - 1 ] ) < 0; j-- )
/* 4*/              a[ j ] = a[ j - 1 ];
/* 5*/          a[ j ] = tmp;
            }
        }

        /**
         * @see 希尔排序
         * Shellsort, using Shell's (poor) increments.
         * @param a an array of Comparable items.
         *todo 第一层for循环:改变gap的值，决定最终终止条件，最后的gap的值肯定是1
         *todo 第二层for循环:i=gap，每一次进入从当前a[gap]位置开始，i++，一步步向后走直到a.length(在这一层tem=a[gap]，
         *todo 在引起的第三层中的比较与交换元素，都是以当前tmp为参考小于当前tmp的向后移至a[j]，初始a[j]为a[i]=tmp,
         *todo 如果当gap值较小时，第三层可能会有会有多次a[ j ] = a[ j - gap ]操作：效果就是以当前gap为步长，以a[i]=tmp为起点进行a[j]=a[j-gap]的循环操作
         *todo 直到不满足条件，最后再通过a[ j ] = tmp将初始的tmp(a[i])--->a[j]，此时的j为最后一次a[j]=a[j-gap]中的[j-gap]因为，进行完此操作后，
         *todo 会执行j-=gap，即将tmp赋值给最后向后移(向后赋值)的节点)
         *todo 第三层for循环:只有在第一次进循环就满足j>=gap&&tmp.compareTo(a[j-gap])的情况下，才会发生，第三层的赋值，配合最后的a[j]=tmp来完成一次或多级交换(参见上)
         *todo 在算法刚开始时，gap比较大，进行过一次j-=gap后肯定不再满足循环条件，此时配合着第二层的循环，效果:每一次tmp(a[i])与a[j-gap](此时i=j),比较，
         *todo 若满足条件，配合最后的a[j=i-gap]=tmp实现交换，就像以gap为步长进行一次a[i]与a[i-gap]的交换一样。
         *todo 至于第三层要满足j>=gap的原因:如果j<2gap，此时要是再满足tmp<a-[i-gap]进行交换时,a[j-gap]会数组越界异常，(加入可以运行到)之后会执行j-=gap，也会j<0，
         */
        public static void shellsort( Comparable [ ] a )
        {
            int j;
/* 1*/      for( int gap = a.length / 2; gap > 0; gap /= 2 )
/* 2*/          for( int i = gap; i < a.length; i++ )
                {
/* 3*/              Comparable tmp = a[ i ];
/* 4*/              for( j = i; j >= gap &&
                                tmp.compareTo( a[ j - gap ] ) < 0; j -= gap )
/* 5*/                  a[ j ] = a[ j - gap ];
/* 6*/              a[ j ] = tmp;
                }
        }


        /**
         * Standard heapsort.
         * 堆排序
         * @param a an array of Comparable items.
         */
        public static void heapsort( Comparable [ ] a )
        {
            /*todo 二叉堆biludHeap涉及到*2的儿子，所以条件(a.length / 2)*/
/* 1*/      for( int i = a.length / 2; i >= 0; i-- )  /* buildHeap *//*todo 通过由下到上的执行下滤(由上至下)完成由下到上的排序!!!*/
            /*todo 从后(a.length/2)向0方向循环，从下向上下滤，先处理好下边与子的关系，再向上走也就只用处理与子的大小关系啦!!!*/
/* 2*/          percDown( a, i, a.length );
/* 3*/      for( int i = a.length - 1; i > 0; i-- )
            {
/* 4*/          swapReferences( a, 0, i );            /* deleteMax */
/* 5*/          percDown( a, 0, i );
            }
        }

        /**
         * Internal method for heapsort.
         * @param i the index of an item in the heap.
         * @return the index of the left child.
         */
        private static int leftChild( int i )
        {
            /*todo 因为是从零开始，所以左儿子的位子2*i+1*/
            return 2 * i + 1;
        }

        /**
         * Internal method for heapsort that is used in
         * deleteMax and buildHeap.
         * @see 下滤,由上至下
         * @see 通过deleteMax方法删除最大项(实际是swapReferences()方法将最大值与将要腾出的后边的第i个位置交换,继而将后部的一个小值换到a[0]
         * @see 进而引起堆从上到下的调整(为了保持堆得的完整与性质,不能说从root的儿子里选一个较大的放到root有空洞，破坏堆结构)
         * @param a an array of Comparable items.
         * @index i the position from which to percolate down.
         * @int n the logical size of the binary heap.
         */
        private static void percDown( Comparable [ ] a, int i, int n )
        {
            int child;
            Comparable tmp;

/* 1*/      for( tmp = a[ i ]; leftChild( i ) < n; i = child )
            {
/* 2*/          child = leftChild( i );
                /*todo 如果左儿子小于右儿子，则child++,与二叉堆相反，所以的是max堆*/
/* 3*/          if( child != n - 1 && a[ child ].compareTo( a[ child + 1 ] ) < 0 )
/* 4*/              child++;
                /*todo 开时下滤时的位置,(tmp = a[ i ])小于较大孩子时，交换位置，较大的孩子上升，*/
                /*todo 在整个循环中，将大于tmp的项逐渐上盛一个位置，再将tem放到他该到的位置*/
                /*todo 只要项大于tmp则父亲->root,儿子->父亲，孙子->儿子，重孙子->孙子(条件是均大于tem)*/
/* 5*/          if( tmp.compareTo( a[ child ] ) < 0 )
/* 6*/              a[ i ] = a[ child ];
                else
/* 7*/              break;
            }
/* 8*/      a[ i ] = tmp;
        }

        /**
         * @see 归并排序
         * @see 分治思想
         * @see 基本的操作是合并两个已排序的表(merge),详情见书第七章
         * @see 递归的将前半部分数据(相对)和后半部分数据(相对)各自归并排序,递归历程中merge()
         * Mergesort algorithm.
         * @param a an array of Comparable items.
         */
        public static void mergeSort( Comparable [ ] a )
        {
            Comparable [ ] tmpArray = new Comparable[ a.length ];

            mergeSort( a, tmpArray, 0, a.length - 1 );
        }

        /**
         * Internal method that makes recursive calls.
         * @param a an array of Comparable items.
         * @param tmpArray an array to place the merged result.
         * @param left the left-most index of the subarray.
         * @param right the right-most index of the subarray.
         */
        private static void mergeSort( Comparable [ ] a, Comparable [ ] tmpArray,
                   int left, int right )
        {
            if( left < right )
            {
                int center = ( left + right ) / 2;
                 /*todo 执行顺序的分析，先把第一个mergeSort()执行，第一个mergeSort()引发的mergeSort()也先执行，才会进入第二个
                 * todo mergeSort()，但是第二个mergeSort()引发mergeSort()后包含第一个和第二个mergeSort()，在按照第一个mergeSort()优先执行完（递归的执行完成例程）
                 * todo 在进入第二个mergeSort()，直到结束!!!*/
                mergeSort( a, tmpArray, left, center );
                mergeSort( a, tmpArray, center + 1, right );
                merge( a, tmpArray, left, center + 1, right );
            }
        }

        /**
         * @see 由于merge是mergeSoft的最后一行,因此在任意时刻只需要一个临时数组在活动,这个临时数组在
         * @see mergeSoft驱动程序建立,而且对应进入merge()是的不同其实index我们一直复用这个临时数组对应的
         * @see index位置,在不断的递归进入,此临时数组也在不断的演变
         * Internal method that merges two sorted halves of a subarray.
         * @param a an array of Comparable items.
         * @param tmpArray an array to place the merged result.
         * @param leftPos the left-most index of the subarray.
         * @param rightPos the index of the start of the ssl half.
         * @param rightEnd the right-most index of the subarray.
         */
        private static void merge( Comparable [ ] a, Comparable [ ] tmpArray,
               int leftPos, int rightPos, int rightEnd )
        {
            int leftEnd = rightPos - 1;
            int tmpPos = leftPos;
            int numElements = rightEnd - leftPos + 1;

            // Main loop
            while( leftPos <= leftEnd && rightPos <= rightEnd )
                if( a[ leftPos ].compareTo( a[ rightPos ] ) <= 0 )
                    tmpArray[ tmpPos++ ] = a[ leftPos++ ];
                else
                    tmpArray[ tmpPos++ ] = a[ rightPos++ ];

            while( leftPos <= leftEnd )    // Copy rest of first half
                tmpArray[ tmpPos++ ] = a[ leftPos++ ];

            while( rightPos <= rightEnd )  // Copy rest of right half
                tmpArray[ tmpPos++ ] = a[ rightPos++ ];

            // Copy tmpArray back
            for( int i = 0; i < numElements; i++, rightEnd-- )
                a[ rightEnd ] = tmpArray[ rightEnd ];
        }

        /**
         * Quicksort algorithm.
         * @param a an array of Comparable items.
         */
        public static void quicksort( Comparable [ ] a )
        {
            quicksort( a, 0, a.length - 1 );
        }

        private static final int CUTOFF = 3;

        /**
         * Method to swap to elements in an array.
         * @see 将最大值与将要腾出的后边的第i个位置交换,继而将后部的一个小值换到a[0]
         * @see 进而引起堆从上到下的调整(为了保持堆得的完整与性质,不能说从root的儿子里选一个较大的放到root有空洞，破坏堆结构)
         * @param a an array of objects.
         * @param index1 the index of the first object.
         * @param index2 the index of the ssl object.
         */
        /*todo 当swapReferences以final形式，很多编译器会以直接插入的方式编译这些代码，而不是方法调用，会提升运行速度！！*/
        public static final void swapReferences( Object [ ] a, int index1, int index2 )
        {
            Object tmp = a[ index1 ];
            a[ index1 ] = a[ index2 ];
            a[ index2 ] = tmp;
        }

        /**
         * @see 取中值
         * Return median of left, center, and right.
         * Order these and hide the pivot.
         */
        private static Comparable median3( Comparable [ ] a, int left, int right )
        {
            int center = ( left + right ) / 2;
            if( a[ center ].compareTo( a[ left ] ) < 0 )
                swapReferences( a, left, center );/*todo 保证C>L*/
            if( a[ right ].compareTo( a[ left ] ) < 0 )
                swapReferences( a, left, right );/*todo 保证R>L*/
            if( a[ right ].compareTo( a[ center ] ) < 0 )
                swapReferences( a, center, right );/*todo 保证R>C*/
            /*todo 最后R>C>P*/
                // todo Place pivot(枢轴元) at position right - 1
            /*todo 通过排序Left已经确定大于枢纽元，不再参与本次第三步(走i,j)*/
            swapReferences( a, center, right - 1 );
            return a[ right - 1 ];
        }

        /**
         * @see 算是尾递归,递归调用之后没有其他操作
         * @see 排序细节上的不同是(不同于归并排序!!!),外层排序,有一定秩序后进入内层排序,最终的小处排序在后层递归里完成,不必再回到外城递归处理!!!
         * Internal quicksort method that makes recursive calls.
         * Uses median-of-three partitioning and a cutoff of 10.
         * @param a an array of Comparable items.
         * @param left the left-most index of the subarray.
         * @param right the right-most index of the subarray.
         */
        private static void quicksort( Comparable [ ] a, int left, int right )
        {
/* 1*/      if( left + CUTOFF <= right )
            {
                /**todo 枢轴元,位于a[ right - 1 ],Left已经确定大于枢纽元，不再参与本次第三步(走i,j)*/
/* 2*/          Comparable pivot = median3( a, left, right );

                    /**todo Begin partitioning  枢轴元位于a[ right - 1 ]*/
/* 3*/          int i = left, j = right - 1;
                /*todo 遇到一次i,j停止就交换一次，之后继续下次循环，在i,j基础上继续前进，直到i,j交错！！！*/
/* 4*/          for( ; ; )
                {
                    /*todo a[i=0]是取中值时的left以确定小于枢纽元,故不需要在判断;初始j=right-1是枢纽元,故不需要判断!!!*/
/* 5*/              while( a[ ++i ].compareTo( pivot ) < 0 ) { }/*todo 当前条件下,当遇到等于枢纽元时也会停止啦!!!*/
/* 6*/              while( a[ --j ].compareTo( pivot ) > 0 ) { }/*todo 当前条件下,当遇到等于枢纽元时也会停止啦!!!*/
                    /*todo i,j都遇到停止点,while结束,此时i,j尚未交错,则简化a[i],a[j]的值*/
/* 7*/              if( i < j )
/* 8*/                  swapReferences( a, i, j );
                    else
                        /*todo i,j交错(i=j||i>j)，break*/
/* 9*/                  break;
                }

/*10*/          swapReferences( a, i, right - 1 );   /* todo Restore pivot交换a[i]与枢纽元,a[i]左小于枢纽元，右大于枢纽元!!!*/

/*11*/          quicksort( a, left, i - 1 );    // todo Sort small elements又会判断是否太小（这里:size小于3），太小采用插入排序,不这么做也可以，不过效率低一些
/*12*/          quicksort( a, i + 1, right );   // todo Sort large elements
            }
            else
                /* todo Do an insertion sort on the subarray元素太少采用插入排序！！！*/
/*13*/          insertionSort( a, left, right );
        }

        /**
         * Internal insertion sort routine for subarrays
         * that is used by quicksort.
         * @param a an array of Comparable items.
         * @param left the left-most index of the subarray.
         * @param right the right-most index of the subarray.
         */
        private static void insertionSort( Comparable [ ] a, int left, int right )
        {
            for( int p = left + 1; p <= right; p++ )
            {
                Comparable tmp = a[ p ];
                int j;

                for( j = p; j > left && tmp.compareTo( a[ j - 1 ] ) < 0; j-- )
                    a[ j ] = a[ j - 1 ];
                a[ j ] = tmp;
            }
        }

        /**
         * Quick selection algorithm.
         * Places the kth smallest item in a[k-1].
         * @param a an array of Comparable items.
         * @param k the desired rank (1 is minimum) in the entire array.
         */
        public static void quickSelect( Comparable [ ] a, int k )
        {
            quickSelect( a, 0, a.length - 1, k );
        }

        /**
         * @see 前三步等同快速排序的前三步,区别在于第四步,快速排序第四步是最S1,及S2进行递归调用
         * @see 快速查找第四步是如果要找的地k个最小元:当k<=|S1|那么k必在S1中,此时quickSelect(S1,k),如果k=|S1|+1那么
         * @see 此时枢纽元就是k,此时不再递归调用,算法结束,a[k-1],否则,k>\S1\+1,则k位于S2中,是第(k-\S1\-1)个最小元
         * @see 递归调用quickSelect(S2,k-\S1\-1)
         * Internal selection method that makes recursive calls.
         * Uses median-of-three partitioning and a cutoff of 10.
         * Places the kth smallest item in a[k-1].
         * @param a an array of Comparable items.
         * @param left the left-most index of the subarray.
         * @param right the right-most index of the subarray.
         * @param k the desired index (1 is minimum) in the entire array.
         */
        private static void quickSelect( Comparable [ ] a, int left,
                                                int right, int k )
        {
/* 1*/      if( left + CUTOFF <= right )
            {
/* 2*/          Comparable pivot = median3( a, left, right );

                    // Begin partitioning
/* 3*/          int i = left, j = right - 1;
/* 4*/          for( ; ; )
                {
/* 5*/              while( a[ ++i ].compareTo( pivot ) < 0 ) { }
/* 6*/              while( a[ --j ].compareTo( pivot ) > 0 ) { }
/* 7*/              if( i < j )
/* 8*/                  swapReferences( a, i, j );
                    else
/* 9*/                  break;
                }

/*10*/          swapReferences( a, i, right - 1 );   // Restore pivot
                /*todo 当k-1=i时不再进行递归调用，此时枢纽元正好在a[i]即a[i-1]!!!*/
/*11*/          if( k <= i )
/*12*/              quickSelect( a, left, i - 1, k );
/*13*/          else if( k > i + 1 )
/*14*/              quickSelect( a, i + 1, right, k );
            }
            else  // Do an insertion sort on the subarray
/*15*/          insertionSort( a, left, right );
        }


        private static final int NUM_ITEMS = 1000;
        private static int theSeed = 1;

        private static void checkSort( Integer[ ] a )
        {
            for( int i = 0; i < a.length; i++ )
                if( a[ i ].intValue( ) != i )
                    System.out.println( "Error at " + i );
            System.out.println( "Finished checksort" );
        }


        public static void main( String [ ] args )
        {
            Integer [ ] a = new Integer[ NUM_ITEMS ];
            for( int i = 0; i < a.length; i++ )
                a[ i ] = new Integer( i );

            for( theSeed = 0; theSeed < 20; theSeed++ )
            {
                Random.permute( a );
                Sort.insertionSort( a );
                checkSort( a );

                Random.permute( a );
                Sort.heapsort( a );
                checkSort( a );

                Random.permute( a );
                Sort.shellsort( a );
                checkSort( a );

                Random.permute( a );
                Sort.mergeSort( a );
                checkSort( a );

                Random.permute( a );
                Sort.quicksort( a );
                checkSort( a );

                Random.permute( a );
                Sort.quickSelect( a, NUM_ITEMS / 2 );
                System.out.println( a[ NUM_ITEMS / 2 - 1 ].intValue( ) + " " +
                                  NUM_ITEMS / 2 );
            }
        }
    }
